import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 面试题03：数组中重复的数字
 */
public class Offer_03 {
    /**
     * 方法三：原地交换
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(1)
     * <p>
     * 算法思想：遍历数组，第一次遇到数字 x 时，将其交换至索引 x 处；
     * 
     * 而当第二次遇到数字 x 时，一定有 nums[x] = x，此时即可得到一组重复数字。
     */
    public int findRepeatNumber(int[] nums) {
        int i = 0;
        while (i < nums.length) {
            // 若 nums[i] = i，说明此数字已在对应索引位置，无需交换，因此跳过
            if (nums[i] == i) {
                i++;
                continue;
            }
            // 若 nums[nums[i]] = nums[i]，代表索引 nums[i] 处和索引 i 处的元素值都为 nums[i]，
            // 即找到一组重复值，返回此值 nums[i]
            if (nums[i] == nums[nums[i]]) {
                return nums[i];
            }
            // 否则，交换 nums[i] 和 nums[nums[i]]，将此数字交换至对应索引位置
            int tmp = nums[i];
            nums[i] = nums[tmp];
            nums[tmp] = tmp;
        }
        return -1;
    }

    /**
     * 方法二：哈希表
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(n)
     */
    public int findRepeatNumber2(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (set.contains(num)) {
                return num;
            } else {
                set.add(num);
            }
        }
        return -1;
    }

    /**
     * 方法一：排序
     * <p>
     * 时间复杂度：O(nlogn)
     */
    public int findRepeatNumber1(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                return nums[i];
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Offer_03 solution = new Offer_03();
        int[] nums = { 2, 3, 1, 0, 2, 5, 3 };
        int ans = solution.findRepeatNumber(nums);
        System.out.println(ans);
    }
}